\documentclass[12pt,a4]{article}
\input{preamble}




\setcounter{section}{6}

\section{The Graph Score Theorem}



\begin{itemize}
 \item Homework assignment published on Monday, 2018-04-09.
 \item Submit questions and first solution by Sunday, 2018-04-15, 12:00 by
 email to dominik.scheder@gmail.com and the TAs.
 \item You will receive feedback by Wednesday, 2018-04-18.
 \item Submit your final solution by Sunday, 2018-04-22 to me and the two TAs.
\end{itemize}


\input{Ex7-1}


\subsection{Alternative Graphs}

Now we will look at different notions of graphs. As defined in class and in the video
lectures, a graph is a pair $G = (V,E)$ where $V$ is a (usually finite) set, called the {\em vertices},
and $E \subseteq {V \choose 2}$, called the set of {\em edges}.

\paragraph{Multigraphs.} 
A {\em multigraph} is like a graph, but you can have several parallel edges between
two vertices. You cannot, however, have self-loops. That is, there cannot
be an edge from $u$ to $u$ itself. This is an example of a multigraph:

\begin{center}
  \includegraphics[width=0.25\textwidth]{figures/multigraph-score.pdf}
\end{center}

We can define degree and score for multigraphs, too. For example, this multigraph
has score $(4,4,2)$. Obviously no graph
can have this score.


\input{Ex7-234}


\newcommand{\wdeg}{\textnormal{wdeg}}

\paragraph{Weighted graphs.} A weighted graph is a graph in which every edge $e$ has a non-negative weight $w_e$.
In such a graph the {\em weighted degree} of a vertex $u$ is $\wdeg(u) = \sum_{ \{u,v\} \in E} w_{\{u,v\}}$.

\begin{center}
  \includegraphics[width=0.25\textwidth]{figures/weighted-graph-score.pdf}
\end{center}

This is an example of a weighted graph, which has score $(3,2,2)$. Obviously no graph
and no multigraph can have this score.

\input{Ex7-567}

\paragraph{Allowing negative edge weights.} Suppose now we allow negative edge weights, like here:
\begin{center}
  \includegraphics[width=0.25\textwidth]{figures/arbitrary-weighted-graph-score.pdf}
\end{center}
This ``graph with real edge weights'' has score $(2,0,0)$. This score is impossible for
graphs, multigraphs, and weighted graphs with non-negative edge weights.

\input{Ex7-890}

\begin{exercise}
   For each student ID $(a_1,\dots,a_n)$ in your group, check whether 
   this is (1) a graph score, (2) a multigraph score, (3) a weighted graph score, or
   (4) the score of a graph with real edge weights.
   
   Whenever the answer is {\em yes}, show the graph, when it is {\em no}, 
   give a short argument why. 
\end{exercise}

\paragraph{Example Solution.} My work ID is 50411. 
This is a weighted graph score, as shown by this picture:
\begin{center}
\includegraphics[width=0.4\textwidth]{figures/graph-50411.pdf}
\end{center}
This settles (3). It is not a multigraph score, because BLABLABLA. I won't give more details, as it might
give too many hints about Exercise 7.2. Alright, this settles (2). Note that I do {\em not} need to answer 
(4), as this is already answered by (3). Neither do I need to answer (1), as a ``no'' for (2) implies
a ``no'' for (1).


\include{516021910049}


\paragraph{Solution.} Ny name is YimingLiu. My student ID is 516021910379.
We sort it in an non-increasing order (997653211100). And we set aside the 2 "0"s so the sequence is d:(9976532111)
\par It is not a graph score because d':(865421000) is not a score.
\par It is a multigraph score because the sum of degrees is an even number and the largest degree of the vertices is smaller than the sum of other degree of other vertices. As is shown in the picture:
\par It is a weighted graph score. As is shown in the picture:
\par It is the score of a graph with real edge weights. As is shown in the picture:
\begin{center}
\includegraphics[width=0.4\textwidth]{lym1.png}
\includegraphics[width=0.4\textwidth]{lym2.png}
\includegraphics[width=0.4\textwidth]{lym3.png}
\end{center}

I'm Zhou Yiyuan, my student ID is 516021910270. This is a multigraph score, as shown by this picture:\\
\begin{center}
\includegraphics[width=0.4\textwidth]{7-11zyy.png}
\end{center}
 This settles(2). It's not a graph score, because the score of my ID is (000111225679), and the largest degree is 9, which is larger than 8, the quantity of verticals with a non-zero degree except the largest one.

\input{515021910404}
\input{516021910229}

\end{document}
